#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include "lista.h"
#include "hash.h"
#define TAM_INI 10

typedef struct hash_dato{
	char* clave;
	void* valor;
}hash_dato_t;

typedef struct hash{
	size_t cantidad;
	size_t tamanio;
	hash_destruir_dato_t destruir_dato;
	lista_t** tabla;
}hash_t;

typedef struct hash_iter{
	size_t pos;
	hash_t* hash;
	lista_iter_t* lista_iter;
}hash_iter_t;


			/*Funcion de Hashing*/
// Devuelve un indice relacionado a la clave que se pasa.
// Post: Devuelve un numeor entero.		
static size_t fhash(const char* clave, size_t tam){
	size_t hash=0;
	int i;
	size_t s = strlen(clave);
	for(i=0;i < s;i++){
		hash = clave[i] + 31 * hash;
	}
	return hash%tam;
}

// Redimensiona el tamaño del hash a su doble.
// Pre: El hash fue creado.
// Post: Devuelve el hash con los mismos elementos que poseia nuevamente ubicados y con el
// doble de tamaño, devuelve false en caso de error.
static bool hash_redimensionar(hash_t* hash){
	hash_dato_t* auxiliar;
	int i;
	hash_t* viejo = malloc(sizeof(hash_t));
	if(viejo == NULL) return false;
	viejo->destruir_dato = NULL;
	viejo->tamanio = hash->tamanio;
	viejo->cantidad = hash->cantidad;
	viejo->tabla = hash->tabla;
	hash->tamanio = hash->tamanio*2;
	hash->cantidad = 0;
	hash->tabla = calloc(hash->tamanio,sizeof(lista_t*));
	if(hash->tabla==NULL){
		hash->tabla = viejo->tabla;
		hash_destruir(viejo);
		return false;
	}
	for(i=0;i < viejo->tamanio;i++){
		if(viejo->tabla[i] != NULL){
			while(!lista_esta_vacia(viejo->tabla[i])){
				auxiliar = lista_borrar_primero(viejo->tabla[i]);
				hash_guardar(hash,auxiliar->clave,auxiliar->valor);
				free(auxiliar->clave);
				free(auxiliar);
			}
		}
	}
	hash_destruir(viejo);
	return true;
}

			

			/*Primitivas básicas*/

hash_t *hash_crear(hash_destruir_dato_t destruir_dato){
	hash_t* mihash = malloc(sizeof(hash_t));
	if (mihash == NULL) return NULL;
	mihash->tabla = calloc(TAM_INI,sizeof(lista_t*));
	if(mihash->tabla == NULL){
		free(mihash);
		return NULL;
	}
	mihash->tamanio = TAM_INI;
	mihash->cantidad = 0;
	mihash->destruir_dato = destruir_dato;
	return mihash;
}

// Modifica el valor relacionado a una clave
// Pre: El hash fue creado.
// Post: modifico el valor que tenia relacionada esa clave eliminando el viejo y guardando
// el nuevo, devuelve false en caso de error.
static bool hash_modificar (hash_t *hash, const char *clave, void *dato){
	int indice = fhash(clave,hash->tamanio);
	lista_iter_t* iterador = lista_iter_crear(hash->tabla[indice]);
	if(iterador==NULL) return false;
	hash_dato_t* actual = lista_iter_ver_actual(iterador);
	while (!lista_iter_al_final(iterador) && strcmp(clave,actual->clave) !=0){
		lista_iter_avanzar(iterador);
		actual = lista_iter_ver_actual(iterador);
	}
	if(lista_iter_al_final(iterador)) return false;
	if(hash->destruir_dato != NULL) hash->destruir_dato(actual->valor);
	actual->valor = dato;
	lista_iter_destruir(iterador);
	return true;
}


bool hash_guardar(hash_t *hash, const char *clave, void *dato){
	if(hash_pertenece(hash,clave)) {
		hash_modificar(hash,clave,dato);
		return true;
	}
	char* copia_clave;
	hash_dato_t* nuevo_dato = malloc(sizeof(hash_dato_t));
	if (nuevo_dato == NULL) return false;
	copia_clave = strdup(clave);
	if(copia_clave==NULL){
		free(nuevo_dato);
		return false;
	}
	nuevo_dato->clave = copia_clave;
	nuevo_dato->valor = dato;
	int indice = fhash(clave,hash->tamanio);
	if(hash->tabla[indice] == NULL){
		hash->tabla[indice] = lista_crear();
		if (hash->tabla[indice] == NULL){
			free(copia_clave);
			free(nuevo_dato);
			return false;
		}
	}
	if(!lista_insertar_primero(hash->tabla[indice],nuevo_dato)) return false;
	hash->cantidad ++;
	if(hash->cantidad >= hash->tamanio*2){
		hash_redimensionar(hash);
	}
	return true;
}


void *hash_borrar(hash_t *hash, const char *clave){
	void* valor_borrado;
	hash_dato_t* dato_borrado;
	hash_dato_t* actual;
	int indice = fhash(clave,hash->tamanio);
	if(hash->tabla[indice] == NULL) return NULL;
	lista_iter_t* iterador = lista_iter_crear(hash->tabla[indice]);
	if(iterador==NULL) return NULL;
	actual = lista_iter_ver_actual(iterador);
	while (!lista_iter_al_final(iterador) && strcmp(clave,actual->clave) !=0){
		lista_iter_avanzar(iterador);
		actual = lista_iter_ver_actual(iterador);
	}
	if(lista_iter_al_final(iterador)){
		lista_iter_destruir(iterador);
		return NULL;
	}
	dato_borrado = lista_borrar(hash->tabla[indice],iterador);
	valor_borrado = dato_borrado->valor;
	free(dato_borrado->clave);
	free(dato_borrado);
	lista_iter_destruir(iterador);
	hash->cantidad --;
	return valor_borrado;
}


void *hash_obtener(const hash_t *hash, const char *clave){
	int indice = fhash(clave,hash->tamanio);
	if(hash->tabla[indice]==NULL) return false;
	hash_dato_t* actual;
	lista_iter_t* iterador;
	iterador = lista_iter_crear(hash->tabla[indice]);
	if(iterador==NULL) return NULL;
	actual = lista_iter_ver_actual(iterador);
	while (!lista_iter_al_final(iterador) && strcmp(clave,actual->clave) !=0){
		lista_iter_avanzar(iterador);
		actual = lista_iter_ver_actual(iterador);
	}
	if(lista_iter_al_final(iterador)){
		lista_iter_destruir(iterador);
		return NULL;
	}
	lista_iter_destruir(iterador);
	return actual->valor;
}


bool hash_pertenece(const hash_t *hash, const char *clave){
	size_t indice;
	lista_iter_t* iterador;
	hash_dato_t* actual;
	indice = fhash(clave,hash->tamanio);
	if (hash->tabla[indice]== NULL) return false;
	iterador = lista_iter_crear(hash->tabla[indice]);
	actual = lista_iter_ver_actual(iterador);
	while ((!lista_iter_al_final(iterador)) && (strcmp(clave,actual->clave) !=0)){
		lista_iter_avanzar(iterador);
		actual = lista_iter_ver_actual(iterador);
	}
	if(lista_iter_al_final(iterador)){
		lista_iter_destruir(iterador);
		return false;
	}
	lista_iter_destruir(iterador);
	return true;
	
}


size_t hash_cantidad(const hash_t *hash){
	return hash->cantidad;
}


void hash_destruir(hash_t *hash){
	int i;
	hash_dato_t* aux;
	for(i=0;i<hash->tamanio;i++){
		if (hash->tabla[i] != NULL){
			while(!lista_esta_vacia(hash->tabla[i])){
				aux = lista_borrar_primero(hash->tabla[i]);
				if(hash->destruir_dato != NULL) hash->destruir_dato(aux->valor);
				free(aux->clave);
				free(aux);
			}
			lista_destruir(hash->tabla[i],NULL);
		}
	}
	free(hash->tabla);
	free(hash);
}

			 /*Primitivas de iteración*/
			 	 
hash_iter_t *hash_iter_crear(const hash_t *hash){
	hash_iter_t* iter;
	iter = malloc(sizeof(hash_iter_t));
	if(iter == NULL) return NULL;
	iter->pos = 0;
	iter->hash = hash;
	int i;
	for(i=0;i<iter->hash->tamanio;i++){
		if(iter->hash->tabla[i] != NULL && !lista_esta_vacia(iter->hash->tabla[i])){
			iter->pos = i;
			iter->lista_iter = lista_iter_crear(iter->hash->tabla[i]);
			if(iter->lista_iter == NULL){
				free(iter);
				return NULL;
			}
			break;
		}
	}
	if(i == iter->hash->tamanio){
		iter->pos = iter->hash->tamanio;
		iter->lista_iter = NULL;
	}
	return iter;
}


bool hash_iter_avanzar(hash_iter_t *iter){
	if(hash_iter_al_final(iter)) return false;
	lista_iter_t* iterador_auxiliar = iter->lista_iter;
	lista_iter_avanzar(iter->lista_iter);
	if(lista_iter_al_final(iter->lista_iter)){
		int i;
		for(i=iter->pos+1;i<iter->hash->tamanio;i++){
			if(iter->hash->tabla[i] != NULL && !lista_esta_vacia(iter->hash->tabla[i])){
				iter->pos = i;
				iter->lista_iter = lista_iter_crear(iter->hash->tabla[i]);
				if(iter->lista_iter == NULL){
					iter->lista_iter = iterador_auxiliar;
					return false;
				}
				lista_iter_destruir(iterador_auxiliar);
				break;
			}
		}
		if(i == iter->hash->tamanio){
		iter->pos = iter->hash->tamanio;
		lista_iter_destruir(iter->lista_iter);
		iter->lista_iter = NULL;
		}	
	}
	return true;
}


const char *hash_iter_ver_actual(const hash_iter_t *iter){
	hash_dato_t* actual;
	if(hash_iter_al_final(iter)) return NULL;
	actual = lista_iter_ver_actual(iter->lista_iter);
	return actual->clave;
}


bool hash_iter_al_final(const hash_iter_t *iter){
	if(iter->pos == iter->hash->tamanio) return true;
	return false;
}


void hash_iter_destruir(hash_iter_t* iter){
	if(iter->lista_iter!=NULL) lista_iter_destruir(iter->lista_iter);
	free(iter);
}
